This specification relates to networking protocols, specifically to protocols for building and maintaining multiple “trees” in a network and using the trees to route messages through the network.
Generally speaking, a network consists of one or more nodes joined by one or more links. Graphs are a common abstraction for networking applications. The nodes of the network are considered the vertices of a graph and the links between nodes are considered the edges of the graph.
Various graph theory problems are relevant to networks. For example, the distributed all pairs shortest paths problem requires determining the shortest path between all nodes in the graph (or network). The “shortest path” between two nodes is defined as the path between the two nodes with a lowest path-cost. Path-cost is the sum of the weights of each edge on a path; however, the definition of “weight” can vary.
Several solutions have been proposed to the distributed all pairs shortest paths problem, such as the Bellman-Ford algorithm and Dijkstra's algorithm. However, these solutions are slow to respond to changes in the graph. They also require a “god's eye view” of the graph, i.e., knowledge of all nodes and edges in the graph. This knowledge can be stored, for example, as an adjacency table that lists the neighboring nodes of each node.